package com.algorithm.dp;

/**
 * 最长上升子序列问题 : 给出一个数组,求出最长上升子序列
 */
public class LongestIncreasingSequence {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 9, 5, 2, 7, 3, 4, 15};
        lis00(arr);
    }

    /**
     * 若每个子串dp[i] = max{dp[0],dp[1],...,dp[i]} dp[i]表示子数组arr[0:i]且以arr[i]结尾的最长子串长度
     * 再次扫描dp找出最大值即可  -->可以优化为循环内比较
     *
     * @param arr
     */
    private static void lis00(int[] arr) {
        int[] dp = new int[arr.length];
        int max = 1;
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                /**
                 * arr[j] < arr[i] && dp[j] + 1 > dp[i]
                 * 若要更新dp[i]必须满足的条件:
                 *  子dp所在位置的数组值小于当前数组值(因为我们要的是以arr[i]结尾的最长子串长度)
                 *  子dp+1(因为子dp以当前值结尾,所以如果使用肯定是要+1的)大于当前dp
                 */
                if (arr[j] < arr[i]) {
                    int dpUseThisSub = dp[j] + 1;
                    if (dpUseThisSub > dp[i]){
                        dp[i] = dpUseThisSub;
                    }
                }
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        System.out.println(max);
    }


}
